package com.felix.algorithms.sort;

import com.google.common.collect.Lists;

import java.util.Arrays;
import java.util.List;

/**
 * MyHeapSort
 *
 * @author xuejinhua
 * @date 2018/11/2 14:25
 */
public class MyHeapSort {

    public static void main(String[] args) {
        List<Integer> list = Lists.newArrayList(1, 2, 8, 9, 5, 7, 6, 3, 4);
        sort(list);
        System.out.println(list);
    }


    public static void sort(int[] array) {
        buildMaxHeapify(array);
        int length = array.length;
        for (int i = 0; i < length; i++) {
            swap(array, 0, length - i - 1);
            maxHeapify(array, 0, length - i - 1);
        }
    }

    public static void buildMaxHeapify(int[] array) {
        int size = (array.length >> 1) - 1;
        for (int i = 0; i < size + 1; i++) {
            maxHeapify(array, size - i, array.length);
        }
    }


    private static void swap(int[] array, int max, int i) {
        int temp = array[i];
        array[i] = array[max];
        array[max] = temp;
    }

    private static <T> void swap(List<T> heapSequence, int x, int y) {
        T value = heapSequence.set(y, heapSequence.get(x));
        heapSequence.set(x, value);
    }

    public static <T extends Comparable<? super T>> void buildMaxHeapify(List<T> heapSequence) {
        int size = (heapSequence.size() >> 1) - 1;
        for (int i = 0; i < size + 1; i++) {
            maxHeapify(heapSequence, size - i, heapSequence.size());
        }
    }

    public static void maxHeapify(int[] array, int i, int length) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int max = i;
        if (left < length && array[max] < array[left]) {
            max = left;
        }
        if (right < length && array[max] < array[right]) {
            max = right;
        }
        if (max != i) {
            swap(array, max, i);
            maxHeapify(array, max, length);
        }
    }

    public static <T extends Comparable<? super T>> void maxHeapify(List<T> heapSequence, int i, int length) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int max = i;
        if (left < length && heapSequence.get(max).compareTo(heapSequence.get(left)) < 0) {
            max = left;
        }
        if (right < length && heapSequence.get(max).compareTo(heapSequence.get(right)) < 0) {
            max = right;
        }

        if (max != i) {
            swap(heapSequence, max, i);
            maxHeapify(heapSequence, max, length);
        }
    }

    public static <T extends Comparable<? super T>> void sort(List<T> heapSequence) {
        buildMaxHeapify(heapSequence);
        int length = heapSequence.size();
        for (int i = 0; i < length; i++) {
            swap(heapSequence, 0, length - i - 1);
            maxHeapify(heapSequence, 0, length - i - 1);
        }
    }

}
